package org.basis.algorithm.graph;

import org.basis.algorithm.graph.common.Graph;
import org.basis.algorithm.graph.common.Node;

import java.util.*;

/**
 * 拓扑排序
 * 拓扑排序在工程上最常用于编译分析依赖关系
 * 适用范围:要求有向图，且有入度为0的节点，且没有环
 *
 * @author Mr_wenpan@163.com 2021/12/23 14:41
 */
public class TopologySort {

    public static void main(String[] args) {
        int[] aa = new int[]{1, 1, 2};
        int i = removeDuplicates(aa);
        System.out.println(i);
    }

    public int[] sortArrayByParity2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        // 指针大法
        int index = 0;
        int left = 0;
        int right = nums.length - 1;
        while (index <= right) {
            if (nums[index] % 2 == 0) {
                int temp = nums[left];
                nums[left] = nums[index];
                nums[index] = temp;
                left++;
                index++;
            } else {
                int temp = nums[left];
                nums[left] = nums[index];
                nums[index] = temp;
                right--;
            }
        }
        return nums;
    }

    public int[] sortArrayByParity(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        LinkedList<Integer> list1 = new LinkedList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                list1.add(num);
            } else {
                list2.add(num);
            }
        }
        int index = 0;
        while (!list1.isEmpty()) {
            nums[index] = list1.poll();
            index++;
        }
        while (!list2.isEmpty()) {
            nums[index] = list2.poll();
            index++;
        }
        return nums;
    }

    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }

    public int singleNonDuplicate2(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 使用hash表记录出现次数
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 找出出现次数为1的数
        for (int num : nums) {
            if (map.get(num) == 1) {
                return num;
            }
        }
        // 没有找到
        return -1;
    }

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int index = 0;
        int left = 0;
        // 指针一直往右移动
        while (index < nums.length) {
            if (nums[index] == nums[left]) {
                index++;
            } else {
                // 左边界外扩
                left++;
                // 交换
                int temp = nums[left];
                nums[left] = nums[index];
                nums[index] = temp;
                index++;
            }
        }
        return left;
    }


    public String[] findOcurrences(String text, String first, String second) {
        if (text == null || "".equals(text) || text.length() <= 2) {
            return null;
        }
        String[] split = text.split(" ");
        List<String> res = new ArrayList<>();
        // 双指针
        int pre = 0;
        int post = 1;
        while (post < split.length - 1) {
            if (split[pre].equals(first) && split[post].equals(second)) {
                res.add(split[post + 1]);
            }
            // 指针后移
            pre = post;
            post = post + 1;
        }

        // 集合转换为数组
        String[] strings = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            strings[i] = res.get(i);
        }

        return strings;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List<Node> topoSort(Graph graph) {
        LinkedList<Node> queue = new LinkedList<>();
        // 存放每个node的入度
        HashMap<Node, Integer> map = new HashMap<>();
        // 遍历图节点，将入度为0的点先入队列
        for (Node node : graph.nodes.values()) {
            map.put(node, node.in);
            if (node.in == 0) {
                queue.add(node);
            }
        }

        List<Node> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            res.add(poll);
            // 遍历他所有邻近的节点
            for (Node next : poll.nexts) {
                // 入度--（插除一个该节点的入度）
                map.put(next, map.get(next) - 1);
                if (map.get(next) == 0) {
                    // 插除入度后如果入度为0 ，则添加到队列
                    queue.add(next);
                }
            }
        }

        // 返回排序结果
        return res;
    }

}
